package com.jjlin.chapter_3;

import java.util.*;

public class CD175{
    //二叉树节点
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static TreeNode createBinaryTree(int[][] nums, int root){
        HashMap<Integer, TreeNode> map = new HashMap<>();
        int rows = nums.length;
        int cols = nums[0].length;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(nums[i][j] != 0 && !map.containsKey(nums[i][j]))
                    map.put(nums[i][j], new TreeNode(nums[i][j]));

        for(int i = 0; i < rows; i++){
            TreeNode node = map.get(nums[i][0]);
            if(nums[i][1] != 0){
                node.left = map.get(nums[i][1]);
                node.left.parent = node;
            }
            if(nums[i][2] != 0){
                node.right = map.get(nums[i][2]);
                node.right.parent = node;
            }
        }
        return map.get(root);
    }

    //查找val为target的节点
    public static TreeNode findTreeNode(TreeNode root, int target){
        if(root == null)
            return root;
        if(root.val == target)
            return root;
        TreeNode left = findTreeNode(root.left, target);
        if(left != null)
            return left;
        TreeNode right = findTreeNode(root.right, target);
        return right;
    }

    //返回node的后继节点
    public static TreeNode getNextTreeNode(TreeNode node){
        if(node == null)
            return node;
        if(node.right != null)
            return getLastMost(node.right);
        TreeNode parent = node.parent;
        TreeNode cur = node;
        while(parent != null && parent.left != cur){
            cur = parent;
            parent = cur.parent;
        }
        return parent;
    }

    //返回node的最左下方的节点
    public static TreeNode getLastMost(TreeNode node){
        if(node == null)
            return node;
        while(node.left != null)
            node = node.left;
        return node;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        TreeNode head = createBinaryTree(nums, root);
        int target = sc.nextInt();
        TreeNode node = findTreeNode(head, target);
        node = getNextTreeNode(node);
        System.out.println(node == null ? 0 : node.val);
    }
}

